package TestSort;

import java.util.Random;

public class ShellSort {

    public static int[] arr = new int[1_0000];

    public static void shellSort (int[] arr, int gap) {
        int i = 0;
        int j = gap;
        int tmp = gap;
        while (tmp != arr.length) {
            if (arr[i] > arr[j]) {
                swap(arr, j, i);
            }
            j = ++tmp;
            i = j - gap;
        }
    }

    public static void swap (int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    public void initiateNotOrderArray() {
        int i = 0;
        Random random = new Random();
        while (i < this.arr.length) {
            arr[i] = random.nextInt(1_0000);
            i++;
        }
    }

    public void initiateOrderArray () {
        int i = 0;
        while (i < this.arr.length) {
            arr[i] = i;
            i++;
        }
    }

    public static long testOrderSpeed () {
        ShellSort shell = new ShellSort();
        shell.initiateOrderArray();
        long startTime = System.currentTimeMillis();
        int gap = arr.length - 1;
        while (gap != 0) {
            shellSort(arr, gap);
            gap /= 2;
        }
        long endTime = System.currentTimeMillis();
        return endTime - startTime;
    }

    public static long testNotOrderSpeed () {
        ShellSort shell = new ShellSort();
        shell.initiateNotOrderArray();
        long startTime = System.currentTimeMillis();
        int gap = arr.length - 1;
        while (gap != 0) {
            shellSort(arr, gap);
            gap /= 2;
        }
        long endTime = System.currentTimeMillis();
        return endTime - startTime;
    }

    public static void main(String[] args) {
        System.out.println(testOrderSpeed());
        for (int x:
             arr) {
            System.out.print(x + " ");
        }
        System.out.println("=========");
        System.out.println(testNotOrderSpeed());
        for (int x:
                arr) {
            System.out.print(x + " ");
        }
    }

    public static void main1(String[] args) {
        int[] arr = new int[] {9,1,2,5,7,4,8,6,3,5};
        int gap = arr.length - 1;
        while (gap != 0) {
            shellSort(arr, gap);
            gap /= 2;
        }
        for (int x:
             arr) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}
